//
//  5_最长回文子串.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/11.
/*
 https://leetcode.cn/problems/longest-palindromic-substring/description/
 给你一个字符串 s，找到 s 中最长的回文
 子串
 。

 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

  

 示例 1：

 输入：s = "babad"
 输出："bab"
 解释："aba" 同样是符合题意的答案。
 示例 2：

 输入：s = "cbbd"
 输出："bb"
 */

import UIKit

class GetLongestPalindrome: NSObject {
    func QA() {
        print(longestPalindrome("abad"))
        print(longestPalindrome("cbbd"))
        print(longestPalindrome("bb"))

        

    }
    // 马拉车算法
    func longestPalindrome(_ s: String) -> String {
        if s.count < 2 { return s }
        let strArray = Array(s)
        let cs = maLaStr(strArray)
        var m = Array(repeating: 0, count: cs.count)
        let count = m.count - 2
        var r = 1
        var c = 1
        var maxLength = 0
        var begin = 0
        for i in 2..<count {
            if r > i {
                let li = c * 2 - i
                if li + m[i] <= r {
                    m[i] = m[li]
                } else {
                    m[i] = r - i
                }
            }
            // 中心法
            while cs[i + m[i] + 1] == cs[i - m[i] - 1] {
                m[i] += 1
            }
            
            if m[i] > maxLength {
                maxLength = m[i]
                begin = (i - m[i]) >> 1
            }

            // 更新c 和r
            if i + m[i] > r {
                c = i
                r = r + m[i]
            }
        }
        let rang = begin..<(begin + maxLength)
        return String(strArray[rang])
    }
     
    private func maLaStr(_ strArray: [Character]) -> [Character] {
        var array: [Character] = ["^", "#"]

        for item in strArray {
            array.append(item)
            array.append("#")
        }
        array.append("$")
        return array
    }
    
    // 扩展中心法
    func longestPalindrome2(_ s: String) -> String {
        if s.count < 2 { return s }
        let strArray = Array(s)
        var maxStr = String(strArray[0])
        for i in (1..<s.count - 1).reversed() {
            let centerStr = palindrome(strArray, i - 1, i + 1)
            let lineStr = palindrome(strArray, i, i + 1)
            if centerStr.count > lineStr.count && centerStr.count >= maxStr.count {
                maxStr = centerStr
            } else if centerStr.count <= lineStr.count && lineStr.count >= maxStr.count {
                maxStr = lineStr
            }
        }
        // 处理0元素右边的分割线
        if strArray[0] == strArray[1] && maxStr.count < 2  {
            maxStr = String(strArray[0...1])
        }
        return maxStr
    }
    
    private func palindrome(_ array: [Character], _ begin: Int, _ end:Int) -> String {
        var begin = begin
        var end = end
        while begin >= 0 && end < array.count && array[begin] == array[end] {
            begin -= 1
            end += 1
        }
        if begin+1 <= end-1{
            let rang = (begin+1)...(end-1)
            let result = String(array[rang])
            return result
        } else {
            return ""
        }
    }
    
//    动态规划
    func longestPalindrome1(_ s: String) -> String {
        if s.count == 0 { return s }
        let strArray = Array(s)
        let array = Array(repeating: false, count: s.count)
        var dp = Array(repeating: array, count: s.count)
        var maxLength = 1
        var maxStr = String(strArray[0])
        for i in (0..<s.count).reversed() {
            for j in (i..<s.count) {
                if strArray[i] == strArray[j] {
                    if (j - i < 2 || dp[i + 1][j - 1]) {
                        dp[i][j] = true
                        let length = j - i + 1
                        if length > maxLength {
                            maxLength = length
                            maxStr = String(strArray[i...j])
                        }
                    }
                } else {
                    dp[i][j] = false
                }
            }
        }
        return maxStr
    }
}
